package random;

/**
 * 寻找旋转排序数组中的最小值
 *
 * 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
 * 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
 * 给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
 */

public class L153 {

    public static void main(String[] args) {
        System.out.println(findMin(new int[]{4,5,6,7,0,1,2}));
    }

/*    0,1,2,3,4
    4,0,1,2,3
    3,4,0,1,2
    2,3,4,0,1
    1,2,3,4,0*/

    public static int findMin(int[] nums) {

        int begin = 0;
        int end = nums.length - 1;
        if (nums.length == 1) return nums[0];
        if (nums[begin] < nums[end] ) return nums[begin];
        while (begin != end) {
            int mid = (end + begin) / 2;
            if (nums[begin] > nums[end] && nums[mid] > nums[end]) {
                begin = mid;
            }else if (nums[begin] > nums[end] && nums[mid] < nums[end]) {
                end = mid;
            }
            if (begin == end - 1) {
                if (nums[begin] > nums[end]) {
                    return nums[end];
                }else {
                    return nums[begin];
                }
            }

        }

        return 0;
    }
}
